package com.example.tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 设计一个使用单词列表进行初始化的数据结构，单词列表中的单词 互不相同。
 * 如果给出一个单词，请判定能否只将这个单词中一个字母换成另一个字母，使得所形成的新单词存在于你构建的字典中。
 * <p>
 * 示例：
 * <p>
 * 输入
 * ["MagicDictionary", "buildDict", "search", "search", "search", "search"]
 * [[], [["hello", "leetcode"]], ["hello"], ["hhllo"], ["hell"], ["leetcoded"]]
 * 输出
 * [null, null, false, true, false, false]
 * <p>
 * 解释
 * MagicDictionary magicDictionary = new MagicDictionary();
 * magicDictionary.buildDict(["hello", "leetcode"]);
 * magicDictionary.search("hello"); // 返回 False
 * magicDictionary.search("hhllo"); // 将第二个 'h' 替换为 'e' 可以匹配 "hello" ，所以返回 True
 * magicDictionary.search("hell"); // 返回 False
 * magicDictionary.search("leetcoded"); // 返回 False
 */
public class Leetcode676_MagicDictionary {
    public static void main(String[] args) {

        MagicDictionary2 magicDictionary = new MagicDictionary2();
        String[] strs = {"hello", "leetcode"};
        magicDictionary.buildDict(strs);
        System.out.println(magicDictionary.search("hello"));
        System.out.println(magicDictionary.search("hhllo"));
        System.out.println(magicDictionary.search("hlllm"));
        System.out.println(magicDictionary.search("hell"));
        System.out.println(magicDictionary.search("leetcoded"));


    }

    /**
     * 解法二:hash表
     *
     * 以字符串长度为key,相同字符长度的字符串组成一个list为value形成一个hash表
     *
     */
    static class MagicDictionary2 {
        // 以字符串长度为key,相同字符长度的字符串组成一个list为value
        private Map<Integer, List<String>> dict;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary2() {
            dict = new HashMap<>();
        }

        public void buildDict(String[] dictionary) {
            for (String word : dictionary) {
//                dict.computeIfAbsent(word.length(), x -> new ArrayList()).add(word);
                dict.computeIfAbsent(
                        word.length(),
                        x -> {
                            List<String> tmp = new ArrayList<>();
                            tmp.add(word);
                            return tmp;
                        });
            }
        }

        /**
         * 先根据字符串长度筛选出与待查询字符串长度相同的字符串list来
         * 然后遍历这数组，如果存在与待查询字符串有且仅有一个字符不同的就返回true,否则false
         *
         * @param searchWord
         * @return
         */
        public boolean search(String searchWord) {
            if (!dict.containsKey(searchWord.length())) {
                return false;
            } else {
                List<String> v = dict.get(searchWord.length());
                for (int i = 0; i < v.size(); i++) {
                    if (getWordDiffCount(v.get(i), searchWord) == 1)
                        return true;
                }
                return false;
            }
        }

        private int getWordDiffCount(String str1, String str2) {
            int count = 0;
            for (int i = 0; i < str1.length(); i++) {
                if (str1.charAt(i) != str2.charAt(i))
                    if (++count > 1)
                        break;
            }
            return count;
        }
    }

    /**
     * 方式一:使用Trie树实现
     */
    static class MagicDictionary {

        private Trie trie;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary() {
            trie = new Trie();
        }

        public void buildDict(String[] dictionary) {
            for (int i = 0; i < dictionary.length; i++) {
                trie.insert(dictionary[i]);
            }
        }

        public boolean search(String searchWord) {
            return trie.searchForOnlyHasOneNotMatch(searchWord);
        }
    }


}
